#define  _CRT_SECURE_NO_WARNINGS
class Solution {

    vector<int> index;
    vector<int> ret;
    vector<int> tmp;
    vector<int> tmp_i;

    void mergeSort(vector<int>& nums, int l, int r)
    {
        if (l >= r) return;
        int mid = (l + r) >> 1;
        mergeSort(nums, l, mid);
        mergeSort(nums, mid + 1, r);
        int i = l, j = mid + 1, cur = l;
        while (i <= mid && j <= r)
        {
            if (nums[i] > nums[j])
            {
                ret[index[i]] += r - j + 1;
                tmp[cur] = nums[i];
                tmp_i[cur++] = index[i++];
            }
            else
            {
                tmp[cur] = nums[j];
                tmp_i[cur++] = index[j++];
            }
        }
        while (i <= mid)
        {
            tmp[cur] = nums[i];
            tmp_i[cur++] = index[i++];
        }
        while (j <= r)
        {
            tmp[cur] = nums[j];
            tmp_i[cur++] = index[j++];
        }
        for (int i = l; i <= r; i++)
        {
            nums[i] = tmp[i];
            index[i] = tmp_i[i];
        }
    }
public:
    vector<int> countSmaller(vector<int>& nums) {
        int n = nums.size();
        index.resize(n);
        ret.resize(n);
        tmp.resize(n);
        tmp_i.resize(n);
        for (int i = 0; i < n; i++) index[i] = i;
        mergeSort(nums, 0, n - 1);
        return ret;
    }
};